920D - Tanks - CodeForces Solution

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<tuple>
#include<set>
#include<map>
using namespace std;
const int MAX_N=5e3+1;
int t;

bool dp[MAX_N][MAX_N];
int Prev[MAX_N][MAX_N];

int a[MAX_N];
int n;
int k;
int v;
bool used[MAX_N];
vector<int>q;
void Do(int i,int rem)
{
    while(Prev[i][rem]!=0)
    {
        q.push_back(Prev[i][rem]);
        used[Prev[i][rem]]=1;
        int n_i=Prev[i][rem]-1;
        int n_rem=(rem-a[Prev[i][rem]]%k+k)%k;
        i=n_i;
        rem=n_rem;
    }
}
int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>k>>v;
    int all=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        all+=a[i];
    }
    if(v==0)
    {
        cout<<"YES"<<"\n";
        if(a[1]!=0)cout<<a[1]/k+(a[1]%k!=0)<<" "<<1<<" "<<2<<"\n";
        return 0;
    }
    if(all<v){cout<<"NO"<<"\n";return 0;}
    if(v%k==0)
    {
        cout<<"YES"<<"\n";
        for(int i=2;i<=n;i++)
        {
            cout<<(a[i]+k-1)/k<<" "<<i<<" "<<1<<"\n";
        }

        cout<<v/k<<" "<<1<<" "<<2<<"\n";
        return 0;
    }

    for(int i=1;i<=n;i++)
    {
        if(a[i]==v)
        {
            cout<<"YES"<<"\n";
            return 0;
        }
    }


    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int rem=0;rem<k;rem++)
        {
            if(dp[i-1][rem])
            {
                dp[i][rem]=1;
                Prev[i][rem]=Prev[i-1][rem];
            }
        }
        for(int rem=0;rem<k;rem++)
        {
            if(dp[i-1][rem])
            {
                dp[i][(rem+a[i]%k)%k]=1;
                Prev[i][(rem+a[i]%k)%k]=i;
            }
        }
    }

    if(dp[n][v%k]==0)
    {
        cout<<"NO"<<"\n";
        return 0;
    }

    Do(n,v%k);

    for(int i=1;i<q.size();i++)
    {
        a[q[0]]+=a[q[i]];
    }

    if(a[q[0]]>=v)
    {
        cout<<"YES\n";

        for(int i=1;i<q.size();i++)
        {
            if((a[q[i]]+k-1)/k!=0)cout<<(a[q[i]]+k-1)/k<<" "<<q[i]<<" "<<q[0]<<"\n";
        }

        if(a[q[0]]!=v)cout<<(a[q[0]]-v)/k<<" "<<q[0]<<" "<<(q[0]==n ? n-1 : n)<<"\n";
    }
    else
    {
        int st=0;

        for(int i=1;i<=n;i++)
        {
            if(used[i])continue;
            st+=a[i];
        }

        if(st/k*k+a[q[0]]<v)
        {
            cout<<"NO"<<"\n";
            return 0;
        }

        cout<<"YES\n";

        for(int i=1;i<q.size();i++)
        {
            if((a[q[i]]+k-1)/k!=0)cout<<(a[q[i]]+k-1)/k<<" "<<q[i]<<" "<<q[0]<<"\n";
        }
        int ul;
        for(int i=1;i<=n;i++)
        {
            if(used[i])continue;
            ul=i;
        }
        for(int i=1;i<=n;i++)
        {
            if(used[i])continue;
            if(i==ul)continue;
           if((a[i]+k-1)/k!=0)cout<<(a[i]+k-1)/k<<" "<<i<<" "<<ul<<"\n";
        }

        if(v!=a[q[0]])cout<<(v-a[q[0]])/k<<" "<<ul<<" "<<q[0]<<"\n";
    }

    return 0;
}